A significant fraction of the improvements in the costs and functions of custom integrated circuits is related to the use of well characterized libraries of standard cells. Such cell libraries provide a variety of building blocks from which more complicated circuits may be constructed. Hence, reducing the time to design and characterize standard cells is highly desirable.
The process of testing and characterizing a new cell is very expensive. Each standard cell may be viewed as having a number of input lines and output lines. To completely test a cell, the response of the cell must be determined for each possible transition of the input lines. Each transition is implemented by changing the state of the input lines. If there are N input lines, there are, in principle. 2.sup.N possible input states. A transition connects two of these input states; hence, the number of possible transitions is the number of different combinations of 2 input states. It is clear that the work to test a cell can rapidly exceed the practical capacity of even the fastest circuit tester or simulator if N is large.
Current methods of generating sequences of input states use a "brute force" strategy. In general, the cell designer can specify a minimal set of allowed transitions of the input lines that the cell is designed to handle. Each transition corresponds to two input states for the cell. In general, each cell also has a constraint on the sequence of input states. For example, in combinational blocks (Those which are not clocked) any transition in which more than one input line changes may cause a race condition. In this case, the constraint requires that no more than one input line change between any two states.
Were it not for this constraint, a test sequence that tests all of the transitions could be generated by sequentially presenting the two states representing the allowed transitions to be tested. For example, consider a first transition represented by the change from state S.sub.1 to S.sub.2, and a second transition which is represented by change From state S.sub.3 to S.sub.4. In the absence of the constraint in question, the test sequence S.sub.1, S.sub.2, S.sub.3, S.sub.4 would be sufficient to test these two transitions. However, in the presence of the constraint, the sequence S.sub.2, S.sub.3 may not be an allowed sequence of input states. In this case, a sequence of states satisfying the constraint, beginning with S.sub.2 and ending with S.sub.3 must be introduced into the test sequence to bring the cell from the test of S.sub.1 -S.sub.2 transition to state S.sub.3 so that the S.sub.3 -S.sub.4 transition can be tested.
The present methods for generating the sequence of states corresponding to the allowed transitions does not take into account the efficiency of the sequence of input states. The only criterion for the test sequence is that all necessary transitions are included. Test sequences created with this method include a high percentage of repeated transitions, and transitions that are meaningless to the characterization of the cell. As a result, it requires approximately one processor-year to complete the characterization of a library of ASIC standard cells, each cell having at most 10 to 15 input lines.
Broadly, it is the object of the present invention to provide an improved method for generating a test sequence for characterizing a circuit.
It is a further object of the present invention to provide a test sequence having fewer repeated states than test sequences generated by prior art methods.
These and other objects of the present invention will become apparent to those skilled in the art from the following a detailed description of the invention and the accompanying drawings.